\documentclass[a4paper,10pt, fleqn]{article}
\usepackage{graphicx} %Paquete para ingresar gráficos.
\usepackage{hyperref}
\usepackage{fancybox}
\usepackage[spanish]{babel} % Para división en sílabas español.
\usepackage[utf8]{inputenc} % Para poner acentos.
\usepackage{placeins} % Para poder usar \FloatBarrier para que las tablas e imagenes no se vayan de la seccion
\usepackage{float} % Para usar [H] en tablas e imagenes


%Encabezado y Pié de página
\input{EncabezadoYPie/EncabezadoyPie.tex}
%Carátula del Trabajo
\title{ \input{Portada/Portada.tex} }

\begin{document}
\maketitle %Hace que el título anterior sea el principal del documento
\newpage

\tableofcontents %Esta línea genera un indice a partir de las secciones y subsecciones creadas en el documento
\newpage

\section{Objetivos}
	El objetivo del presente trabajo consiste en familiarizarnos con las herramientas con las cuales se trabajará en el transcurso de la cursada. Las mismas son:
	\begin{itemize}
	  \item Compilador GCC
	  \item Shell de Unix
	  \item Emulador GXEmul
	  \item Sistema de Composición \LaTeX{}
	\end{itemize}
	Además se aplicarán conocimientos teóricos sobre profiling para poder comparar distintos algoritmos mediante ciertas
mediciones utilizando:
	\begin{itemize}
	  \item Time
	  \item Gprof
	\end{itemize}
	\vspace{1cm}
 
\section{Introducción Teórica}
  \label{sec:InfoTeo}
  Para poner en práctica las herramientas citadas, el presente TP consiste en realizar un programa en el lenguaje C que permita ordenar
  tiras de bytes mediante dos posibles algoritmos de ordenamiento: \emph{Merge-sort} y \emph{Selection-sort}. 
  A continuación se explican brevemente los conceptos necesarios para llevar a cabo esta tarea:

  \vspace{0.5cm}
	\subsection{Shell de Unix}
	  Un shell es un programa intérprete de comandos. Los comandos utilizados en el presente trabajo
	  son los siguientes:
		\begin{itemize}
		  \item \textbf{\emph{pipe}}: Toma lo que se encuentra a la izquierda del pipe como la salida estándar (\emph{stdout}) por defecto y lo pasa como
		      entrada estándar (\emph{stdin}) a lo que se este a la derecha del pipe. Puede servir para pasarle a un programa un
		      archivo y que este lo reciba por la entrada estándar
		  \item \textbf{echo}: Imprime un texto en \emph{stdout}.
		  \item \textbf{cat}: Con este comando se pueden ver, así como también concatenar, varios archivos. 
		    Escribe en la salida estándar.
		\end{itemize}
		\vspace{0.5cm}

	\subsection{Compilador GCC}
		GCC es un compilador gratuito, Open Source y multiplataforma que permite compilar código C. 
		El mismo es un compilador estándar, es decir, que respeta la norma ISOC99 o ANSI dependiendo de su versión, por lo cual se utilizan las 
		bibliotecas estándar para trabajar con el mismo. En esta asignatura el mismo es de gran utilidad dado que permite tener acceso  al código 
		\emph{assembly} equivalente a nuestro programa en C. A continuación se detallan brevemente algunos parámetros que podemos darle al GCC:
		\begin{itemize}
			\item \textbf{-Wall:} Activa todos los warnings.
			\item \textbf{-o file} Almacena la salida del programa en un archivo (\emph{en este caso en file})
			\item \textbf{-O0:} Desactiva las optimizaciones
			\item \textbf{-O3:} Activa todas las optimizaciones
			\item \textbf{-g:} Genera código agregando líneas para el \emph{debbugger}
			\item \textbf{-S:} Detiene el compilador luego de generar el código \emph{assembly}
			\item \textbf{-mrnames(solo para MIPS):} Indica al compilador que genera la salida utilizando 
									 nombre de registro en lugar de número de registro
		\end{itemize}
		Para generar el archivo ``main.s'' con el código \emph{assembly} se debe ejecutar el siguiente comando: 
		  \begin{verbatim}
			      gcc -Wall -O0 -S -mrnames main.c
		  \end{verbatim}
		Para compilar el código se debe ejecutar el siguiente comando:
		\begin{verbatim}
			      gcc -Wall -O0 -o tp0 main.c
		 \end{verbatim}
		\vspace{0.5cm}

	\subsection{Emulador GXEmul}
		Es un emulador gratuito y Open Source de la arquitectuca de computadores MIPS. Tiene como ventajas que puede correr algunos sistemas operativos
		sin modificaciones (especialmente \emph{netBSD}), su portabilidad y velocidad de emulación dado que realiza la traducción binaria en 
		tiempo real. 
		\vspace{0.5cm}
	
	\subsection{Time}
		El comando time permite realizar mediciones en relación al tiempo de ejecución de un programa. Al ejecutar el comando sin opciones, 
		seguido del nombre de un programa y su lista de argumentos:
		\begin{verbatim}
			     time unPrograma arg1 arg2
		\end{verbatim}
		se muestra por pantalla una serie de tiempos, de esta manera:
		\begin{verbatim}
			     real	0m0.137s
			     user	0m0.120s
			     sys	0m0.030s
		\end{verbatim}
                Donde:
                \begin{itemize}
                  \item \textbf{real} es el ``tiempo de reloj'' que toma la ejecución, desde que empieza hasta que termina, incluyendo lapsos utilizados por otros procesos, o durante los cuales el programa está bloqueado esperando I/O.
                  \item \textbf{user} es el tiempo que el código pasa en modo usuario, por ejemplo, ejecutando código de bibliotecas. Sólo tiene en cuenta el tiempo en el que el proceso se está ejecutando.
                  \item \textbf{sys} es el tiempo que el código pasa en el kernel, por ejemplo, haciendo llamadas al sistema. Como el caso anterior, sólo tiene en cuenta el tiempo en el que el proceso se está ejecutando.
                \end{itemize}

                Es decir que para conocer el tiempo de CPU que verdaderamente consume el programa, hay que sumar los tiempos \emph{user} y \emph{sys}.

		\vspace{0.5cm}
	\subsection{Gprof}
		Gprof es un programa que permite conocer información de utilidad sobre el rendimiento de un programa en C. A efectos de este trabajo práctico en particular, nos interesa saber el tiempo de ejecución consumido por cada función del programa.

Para utilizar gprof se debe compilar el código con gcc, con la opción -pg:
                \begin{verbatim}
                gcc -pg -o unPrograma unPrograma.c
                \end{verbatim}
                Una vez compilado, se debe ejecutar el programa normalmente. Esto generará el archivo ``gmon.out'' en el mismo directorio donde está el ejecutable. Finalmente, al ejecutar gprof de la siguiente manera:
                \begin{verbatim}
                gprof unPrograma > reporte.txt
                \end{verbatim}
                se genera el reporte con la información de rendimiento y se almacena en un archivo de texto.

		\vspace{0.5cm}
	\subsection{Algoritmos de ordenamiento}
		A continuación se dan detalles sobre los dos algoritmos de ordenamiento: 
		\begin {itemize}      
		  \item \textbf{\emph{Selection-sort}:}
		    Su orden de complejidad es $O(n^2)$. Consiste en buscar el menor elemento del arreglo y ponerlo en la primera posición, luego buscar el menor elemento del resto del arreglo y ponerlo en segundo lugar, y así sucesivamente.
		 \item	\textbf{\emph{Merge-sort}:}
		    Se basa en la técnica de división y conquista, y tiene complejidad $O(n \log{n})$. Consiste en dividir recursivamente el arreglo en dos sub arreglos, ordenar cada uno por separado, y luego combinarlos en orden. El caso base de la recursión ocurre cuando la longitud del arreglo es 0 o 1, y por lo tanto ya está ordenado.
		\end {itemize}

		
		\vspace{0.5cm}

	\subsection{Ley de Amdahl}
		La ganancia en desempeño que puede ser obtenida mejorando una parte de una computadora puede ser calculada utilizando la ley de Amdahl.
		Esta ley dice que la ganancia en desempeño obtenida utilizando una mejora está limitada por la fracción de tiempo en que esta mejora puede ser utilizada.\\
		La ley de Amdahl define el \emph{speedup} que puede obtenerse una mejora en particular. Que es \emph{speedup}? Supongamos que podemos hacerle una mejora 
		a una máquina que incrementará su desempeño cuando esta sea utilizada, entonces el \emph{speedup} es\\\\
		$Speedup \:= \:\frac{Desempe\tilde{n}o \:para \:la \:tarea \:completa \:utilizando \:la \:mejora \:cuando \:sea \:posible}{Desempe\tilde{n}o \:de \:la \:tarea \:completa \:sin \:usar \:la \:mejora}$\\\\
		Alternativamente,\\\\
		$Speedup \:= \:\frac{Tiempo \:de \:ejecuci\acute{o}n \:para \:la \:tarea \:completa \:sin \:la \:mejora}{Tiempo \:de \:ejecuci\acute{o}n \:de \:la \:tarea \:completa \:utilizando \:la \:mejora \:cuando \:sea \:posible}$\\\\
		El \emph{speedup} nos dice cuanto más rapido una tarea se ejecutará usando la máquina con la mejora en contraposición a la máquina original.
		
		\vspace{1cm}
					
\section{Desarrollo}
	A partir de los conceptos teóricos desarrollados en la sección anterior (\ref{sec:InfoTeo}) se procedió a crear un programa en 
	C que pudiera ordenar bytes a partir de una muestra:
	\vspace{0.5cm}

	\subsection{Modo de Operación}
                Para compilar la aplicación hay que posicionarse en el directorio en el que se encuentra el archivo ``tp0.c'', y ejecutar el siguiente comando:
                \begin{verbatim}
                  gcc -Wall -O0 -o tp0 tp0.c
                \end{verbatim}
 
		La aplicación desarrollada debe recibir ya sea por entrada estándar o mediante archivos de entrada, una muestra de N bytes. 

		\begin{itemize}
			\item \textbf{-s --sel:} Por medio de este comando se indica que el algoritmo de ordenamiento que se va a utilizar es \emph{Selection-sort}.
			\item \textbf{-m --mer:} Por medio de este comando se indica que el algoritmo de ordenamiento que se va a utilizar es \emph{Merge-sort}.
			\item \textbf{-h --help:} Despliega la ayuda.
			\item \textbf{-v --version:} Muestra la versión.
		\end{itemize} 
		
		En caso de no seleccionar ningún algoritmo de ordenamiento, se utilizará por defecto \emph{Merge-sort}.
		\vspace{0.5cm}
	
	\subsection{Ejemplos}
	     Primero, usamos la opcion -h para ver el mensaje de ayuda:
	     \begin{verbatim}
		$tp0 -h
		tp0 [OPTIONS][file...]
		-h, --help	display this help and exit.
		-v, --version	display version information and exit.
		-m, --merge	use the mergesort algorithm.
		-s, --sel	use the selectionsort algorithm.
 	     \end{verbatim}
	     
	     Si quisieramos ordenar los bytes del archivo ``desordenado.txt'', debemos ejecutar
             \begin{verbatim}
                ./tp0 -s desordenado.txt > ordenado.txt
             \end{verbatim}
             Esto ordena el arreglo de bytes, crea el archivo ``ordenado.txt'' y almacena en él el arreglo ordenado. 
	    Si se está ordenando un archivo binario, es recomendable especificar un archivo de salida, como en este caso, y 
	    luego, para visualizar el contenido del archivo binario en formato hexadecimal y separado en bytes, ejecutar el 
	    siguiente comando:
             \begin{verbatim}
                hexdump -C ordenado.txt
             \end{verbatim}
	      En este ejemplo el arreglo de bytes se ordena con el algoritmo \emph{selection sort}; para ordenarlo 
	      utilizando \emph{merge sort}, basta con reemplazar la opción ``s'' por ``m'' (o no indicar ninguna opción, 
	      ya que ese es el algoritmo que el programa usa por defecto). En el caso de que el arreglo a ordenar estuviese
	      compuesto por caracteres imprimibles, puede omitirse indicarle un archivo a la salida estándar y ver el resultado 
	      directamente por consola. De cualquier manera, si se especifica un archivo, este puede verse con cualquier editor 
	      de texto, o por consola con el comando
             \begin{verbatim}
                cat ordenado.txt
             \end{verbatim}
 

\section{Implementación}
	\subsection{Determinaciones Previas}
	  \begin{itemize}
			\item Siempre que se ingrese el parámetro de ayuda (-h o \---help) junto con cualquier otro, se ignorará este último. 
			      Por ejemplo ``echo ``abc'' ./tp0 -h'' sólo muestra el mensaje de ayuda.
			\item Si se seleccionan más de un algoritmo de ordenamiento solo se tendrá en cuenta al primero.
			\item Si alguno de los archivos pasados por parámetro no puede ser leído, la ejecución termina mostrando el error por stderr.
			\item Si se ingresan archivos a través de los argumentos y además alguno por stdin, solo se tendrán en cuenta los primeros, ignorando
			      el ingresado por entrada estándard.
	  \end{itemize}
	

	\subsection{Código Fuente}

\begin{Verbatim}[fontsize=\tiny]

#include <stdio.h>
#include <getopt.h>
#include <stdlib.h>
#include <string.h>

#define TAMANIO_BUFFER 512

enum SELECCION_DE_ALGORITMO {ALGORITMO_SELECCIONADO_MERGE_SORT=1, 
ALGORITMO_SELECCIONADO_SELECTION_SORT=2, ALGORITMO_NO_SELECCIONADO=3};

void swap(char* entrada, int pos1, int pos2) {
	char temp;
	
	temp = entrada[pos1];
	entrada[pos1] = entrada[pos2];
	entrada[pos2] = temp;
}

void selectionSort(char* entrada, int size) {
	int i,j,min;

	for (i=0;i<size;i++) {
		min=i;
		for (j=i+1;j<size;j++) {
			if (entrada[j]<entrada[min])
				min=j;
		}
	if (i!=min)
		swap(entrada,i,min);
	}
}

void mergeBuffers ( char* buffer1, int cantidadDeElementosBuffer1, char* buffer2, 
                                      int cantidadDeElementosBuffer2, char* salida) {
    int indexBuffer1 = 0, indexBuffer2 = 0, indexSalida = 0;
 
    while (	indexBuffer1 < cantidadDeElementosBuffer1 && 
			indexBuffer2 < cantidadDeElementosBuffer2) {
        if (buffer1[indexBuffer1] < buffer2[indexBuffer2]) {
            salida[indexSalida] = buffer1[indexBuffer1];
            indexBuffer1++;
        } else {
            salida[indexSalida] = buffer2[indexBuffer2];
            indexBuffer2++;
        }
        indexSalida++;
    }
    while (indexBuffer1 < cantidadDeElementosBuffer1) {
        salida[indexSalida] = buffer1[indexBuffer1];
        indexBuffer1++;
        indexSalida++;
    }
    while (indexBuffer2 < cantidadDeElementosBuffer2) {
        salida[indexSalida] = buffer2[indexBuffer2];
        indexBuffer2++;
        indexSalida++;
    }    
}
 
void mergeSort(char* entrada, int cantidadDeElementos) {
    char *buffer1 = NULL, *buffer2 = NULL;
    int cantidadDeElementosBuffer1, cantidadDeElementosBuffer2, 
		indexBuffer1, indexBuffer2;
    
    if (cantidadDeElementos > 1) {
		cantidadDeElementosBuffer1 = (int) cantidadDeElementos / 2;
        if (cantidadDeElementos % 2 == 0) {            
			cantidadDeElementosBuffer2 = cantidadDeElementosBuffer1;
        } else {            
            cantidadDeElementosBuffer2 = cantidadDeElementosBuffer1 + 1;
        }
        buffer1 = (char *) malloc(sizeof(char) * cantidadDeElementosBuffer1);
        buffer2 = (char *) malloc(sizeof(char) * cantidadDeElementosBuffer2);
        
        for(indexBuffer1 = 0; indexBuffer1 < cantidadDeElementosBuffer1; 
			indexBuffer1++)
            buffer1[indexBuffer1] = entrada[indexBuffer1];
        for(indexBuffer2 = 0; indexBuffer2 < cantidadDeElementosBuffer2; 
			indexBuffer1++, indexBuffer2++)
            buffer2[indexBuffer2] = entrada[indexBuffer1];
            
        mergeSort(buffer1, cantidadDeElementosBuffer1);
        mergeSort(buffer2, cantidadDeElementosBuffer2);
        mergeBuffers (	buffer1, cantidadDeElementosBuffer1, buffer2,
						cantidadDeElementosBuffer2, entrada);
        free(buffer1);
        free(buffer2);
    }    
}

void mostrarAyuda () {
    printf("tp0 [OPTIONS][file...] \n");
    printf("%-20s %s\n", "-h, --help", "display this help and exit.");
    printf("%-20s %s\n", "-V, --version", "display version information and exit.");
    printf("%-20s %s\n", "-m, --merge", "use the mergesort algorithm.");
    printf("%-20s %s\n", "-s, --sel", "use the selectionsort algorithm.");
}

void mostrarVersion () {
	printf("Versión: 1.0\n");
}

FILE* abrirArchivo(const char *direccion,  const char * modo) {
	FILE *archivo = fopen(direccion, modo);
	if (!archivo) {
		fprintf(stderr,"No se pudo abrir el archivo: %s en modo %s\n",
direccion, modo);
		exit(EXIT_FAILURE);
	}
	return archivo;
}

void ordenarConSelectionSort(char* entrada, char** salida, int tamanioDeDatos) {
	selectionSort(entrada, tamanioDeDatos);
	memcpy(*salida, entrada, tamanioDeDatos);
}

void ordenarConMergeSort(char* entrada, char** salida, int tamanioDeDatos) {
	mergeSort(entrada, tamanioDeDatos);
	memcpy(*salida, entrada, tamanioDeDatos);
}

void ordenarSegunAlgoritmoElegido (enum SELECCION_DE_ALGORITMO seleccion,
			 char* datosEntada,char** datosSalida,int tamanioDeDatos) {
	switch (seleccion) {
		case ALGORITMO_SELECCIONADO_SELECTION_SORT:
			ordenarConSelectionSort(datosEntada, datosSalida, 
                                                             tamanioDeDatos);
			break;
		default:
			// X defecto Merge-Sort.
			ordenarConMergeSort(datosEntada, datosSalida,tamanioDeDatos);
			break;
	}
}

void leerArchivoYObtenerDatos (FILE* archivo,char **datosParseados,
                                                    int *pTamanioTotalDeDatos) {

	char *buffer = (char*) malloc (sizeof(char) * TAMANIO_BUFFER);
	int bytesLeidos = 0 , bytesTotales = 0, numeroDeBuffers = 1, offset = 0;
	int tamanioAnteriorDeDatos = 0;

	while (!feof(archivo)) {
		bytesLeidos = fread(buffer + offset, sizeof(char), TAMANIO_BUFFER, 
                                                                   archivo);
		bytesTotales += bytesLeidos;
		if (bytesLeidos == TAMANIO_BUFFER) {
			numeroDeBuffers ++;
			buffer = (char*)realloc(buffer,
                                     sizeof(char)*TAMANIO_BUFFER*numeroDeBuffers);
			offset += TAMANIO_BUFFER;
		}
	}

	tamanioAnteriorDeDatos = *(pTamanioTotalDeDatos);

	// Actualizo la nueva cantidad de datos
	(*pTamanioTotalDeDatos) += bytesTotales;
	(*datosParseados) = (char*)realloc(*datosParseados,
                                           sizeof(char)* (*pTamanioTotalDeDatos));

	memcpy ((*datosParseados) + tamanioAnteriorDeDatos, buffer, bytesTotales);
	free (buffer);
}

void escribirSalida (FILE* salida, char* datos, int tamanioTotalDeDatos) {
	fwrite(datos, sizeof(char), tamanioTotalDeDatos, salida);
}

int main (int argc, char **argv) {
	FILE *archivoDeEntradaStandar = stdin;
	int opcionElegida = 0, cantidadDeArchivosDeEntrada = 0, 
        tamanioTotalDeDatos = 0;
	int *pTamanioTotalDeDatos = &tamanioTotalDeDatos;
	enum SELECCION_DE_ALGORITMO algoritmoSeleccionado = ALGORITMO_NO_SELECCIONADO;
	char *datosDeEntradas = NULL, *datosOrdenados = NULL;
	char **archivosDeEntrada = NULL;

	/* Una cadena que lista las opciones cortas válidas */
	const char* const opcionesCortas = "hvms";

	/* Una estructura de varios arrays describiendo las opciones largas */
	const struct option opcionesLargas[] = {
	  { "help",	  no_argument, NULL,'h'},
	  { "version", no_argument, NULL,'v'},
	  { "merge",no_argument, NULL,'m'},
	  { "sel",no_argument, NULL,'s'},
	  { NULL,     no_argument, NULL, 0 }
	};

	// Parseo de argumentos.
	while (1) {
		opcionElegida = getopt_long(argc, argv, opcionesCortas, 
                                                        opcionesLargas, NULL);

		if (opcionElegida == -1)
			break;

		switch (opcionElegida) {

			case 'h' : /* -h o --help */
				mostrarAyuda();
				exit(EXIT_SUCCESS);

			case 's' : /* -s o --sel */
				if (algoritmoSeleccionado == ALGORITMO_NO_SELECCIONADO)
				algoritmoSeleccionado = 
                                                ALGORITMO_SELECCIONADO_SELECTION_SORT;
				break;

			case 'm' : /* -m  ó --merge */
				if (algoritmoSeleccionado == ALGORITMO_NO_SELECCIONADO)
				algoritmoSeleccionado = 
                                                ALGORITMO_SELECCIONADO_MERGE_SORT;
			        break;

			case 'v': /* -v  ó --version */
				mostrarVersion();
				exit(EXIT_SUCCESS);

			default :
				mostrarAyuda();
				exit(EXIT_FAILURE);
		}
	}

	// Lectura de datos.
	archivosDeEntrada = argv + optind;
	cantidadDeArchivosDeEntrada = argc - optind;

	if (cantidadDeArchivosDeEntrada > 0) {
		archivoDeEntradaStandar = NULL;
		int i;
		for (i = 0; i<cantidadDeArchivosDeEntrada; ++i) {
			char *path = archivosDeEntrada[i];
			FILE* archivoDeEntrada = abrirArchivo(path, "rb");
			leerArchivoYObtenerDatos (archivoDeEntrada,&datosDeEntradas,
								 pTamanioTotalDeDatos);
			fclose(archivoDeEntrada);
		}
	}else {
		leerArchivoYObtenerDatos (archivoDeEntradaStandar,&datosDeEntradas,
								 pTamanioTotalDeDatos);
	}

	// Ordenar datos.
	datosOrdenados = (char*) malloc (sizeof(char) * tamanioTotalDeDatos);
	memset (datosOrdenados, 0, tamanioTotalDeDatos);

	ordenarSegunAlgoritmoElegido(algoritmoSeleccionado,datosDeEntradas,
                                              &datosOrdenados,tamanioTotalDeDatos);

	// Escritura de datos.
	escribirSalida(stdout, datosOrdenados, tamanioTotalDeDatos);

	free (datosDeEntradas);
	free (datosOrdenados);
	return EXIT_SUCCESS;
} 
\end{Verbatim}

\section{Mediciones}
  Para realizar las mediciones de tiempo de los dos algoritmos se utilizó el comando \emph{time}. El modo de uso de este comando ha sido indicado anteriormente. El tiempo total insumido por el 
  algoritmo es la suma del tiempo \emph{user} y \emph{sys}. Se generaron archivos de tamaño $100*2^N$ bytes con $N$ entre $0$ y $16$ para:
  \begin{itemize}
    \item Un array ya ordenado
    \item Un array en orden inverso
    \item Diez arrays tomados al azar (tomando el promedio de los diez arrays).
  \end{itemize}
  Una vez realizadas todas estas mediciones se calculó para cada valor de N para todos estos archivos el speedup del Mergesort contra el Selection Sort.
  Como el speedup se define como $SU_G=T_{OLD}/T_{NEW}$ tomaremos como $T_{OLD}$ el tiempo insumido por el selection sort y $T_{NEW}$ el tiempo del mergesort.\\
  Vale aclarar que para el caso de las mediciones de tiempo mayores a 30 minutos se toman como infinito, que se da con el algoritmo selection sort para los tamaños más
  grandes de arrays (para $14\le N\le 16$), y por ende el speedup en estos casos termina siendo infinito.\\
  
  \subsection{Medición de arrays ordenados}
    
    \FloatBarrier
    \begin{table}[H]
	\begin{center}
	  \begin{tabular}{|r|r|r|r|r|}
	    \hline
	    \multicolumn{1}{|c|}{N} & \multicolumn{1}{c|}{Tamaño (Bytes)} & \multicolumn{1}{c|}{Merge (s)} & \multicolumn{1}{c|}{Selection (s)} & \multicolumn{1}{c|}{Speedup} \\ \hline
	    0 & 100 & 0.005 & 0.005 & 1.000 \\ \hline
	    1 & 200 & 0.006 & 0.006 & 1.000 \\ \hline
	    2 & 400 & 0.006 & 0.006 & 1.000 \\ \hline
	    3 & 800 & 0.007 & 0.009 & 1.286 \\ \hline
	    4 & 1600 & 0.007 & 0.021 & 3.000 \\ \hline
	    5 & 3200 & 0.008 & 0.04 & 5.000 \\ \hline
	    6 & 6400 & 0.011 & 0.111 & 10.091 \\ \hline
	    7 & 12800 & 0.017 & 0.381 & 22.412 \\ \hline
	    8 & 25600 & 0.024 & 1.467 & 61.125 \\ \hline
	    9 & 51200 & 0.031 & 5.872 & 189.419 \\ \hline
	    10 & 102400 & 0.05 & 23.443 & 468.860 \\ \hline
	    11 & 204800 & 0.091 & 93.896 & 1031.824 \\ \hline
	    12 & 409600 & 0.173 & 375.625 & 2171.243 \\ \hline
	    13 & 819200 & 0.339 & 1500.163 & 4425.260 \\ \hline
	    14 & 1638400 & 0.697 & $\infty$ & $\infty$ \\ \hline
	    15 & 3276800 & 1.425 & $\infty$ & $\infty$ \\ \hline
	    16 & 6553600 & 2.914 & $\infty$ & $\infty$ \\ \hline
	  \end{tabular}
	\end{center}
	\caption{Archivos Ordenados}
	\label{tabla 1}
    \end{table}

    \begin{figure}[H]
      \centering
      \begin{center}
      \includegraphics[width=0.9\textwidth]{msordenados.png}
      \end{center}
      \caption{Tiempos usando el algoritmo mergesort en función del tamaño del array para arrays ordenados}
      \label{fig:1}
    \end{figure}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{ssordenados.png}
      \caption{Tiempos usando el algoritmo selection sort en función del tamaño del array para array ordenados}
      \label{fig:2}
    \end{figure}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{speedupordenados.png}
      \caption{Speedup para arrays ordenados en función de N}
      \label{fig:3}
    \end{figure}
  
  \FloatBarrier
  \subsection{Mediciones de arrays en orden inverso}
  \FloatBarrier
    \begin{table}[H]
      \begin{center}
	\begin{tabular}{|r|r|r|r|r|}
	  \hline
	  \multicolumn{1}{|c|}{N} & \multicolumn{1}{c|}{Tamaño(Bytes)} & \multicolumn{1}{c|}{Merge (s)} & \multicolumn{1}{c|}{Selection (s)} & \multicolumn{1}{c|}{Speedup} \\ \hline
	  0 & 100 & 0.005 & 0.006 & 1.200 \\ \hline
	  1 & 200 & 0.005 & 0.005 & 1.000 \\ \hline
	  2 & 400 & 0.006 & 0.007 & 1.167 \\ \hline
	  3 & 800 & 0.006 & 0.011 & 1.833 \\ \hline
	  4 & 1600 & 0.006 & 0.025 & 4.167 \\ \hline
	  5 & 3200 & 0.007 & 0.038 & 5.429 \\ \hline
	  6 & 6400 & 0.011 & 0.113 & 10.273 \\ \hline
	  7 & 12800 & 0.016 & 0.389 & 24.313 \\ \hline
	  8 & 25600 & 0.024 & 1.496 & 62.333 \\ \hline
	  9 & 51200 & 0.031 & 5.914 & 190.774 \\ \hline
	  10 & 102400 & 0.055 & 23.598 & 429.055 \\ \hline
	  11 & 204800 & 0.094 & 94.832 & 1008.851 \\ \hline
	  12 & 409600 & 0.172 & 375.7 & 2184.302 \\ \hline
	  13 & 819200 & 0.346 & 1500.462 & 4336.595 \\ \hline
	  14 & 1638400 & 0.701 & $\infty$ & $\infty$ \\ \hline
	  15 & 3276800 & 1.423 & $\infty$ & $\infty$ \\ \hline
	  16 & 6553600 & 2.868 & $\infty$ & $\infty$ \\ \hline
	\end{tabular}
     \end{center}
     \caption{Archivos Orden Inverso}
     \label{tabla 2}
    \end{table}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{msinversos.png}
      \caption{Tiempos usando el algoritmo mergesort en función del tamaño del array para arrays en orden inverso}
      \label{fig:4}
    \end{figure}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{ssinversos.png}
      \caption{Tiempos usando el algoritmo selection sort en función del tamaño del array para arrays en orden inverso}
      \label{fig:5}
    \end{figure}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{speedupinversos.png}
      \caption{Speedup para arrays en orden inverso en función de N}
      \label{fig:6}
    \end{figure}
\FloatBarrier
\subsection{Mediciones de arrays aleatorios}
\FloatBarrier
    \begin{table}[H]
      \begin{center}
	\begin{tabular}{|r|r|r|r|r|}
	  \hline
	  \multicolumn{1}{|c|}{N} & \multicolumn{1}{c|}{Tamaño (Bytes)} & \multicolumn{1}{c|}{Merge (s)} & \multicolumn{1}{c|}{Selection (s)} & \multicolumn{1}{c|}{Speedup} \\ \hline
	  0 & 100 & 0.0049 & 0.0068 & 1.388 \\ \hline
	  1 & 200 & 0.0051 & 0.0061 & 1.196 \\ \hline
	  2 & 400 & 0.0056 & 0.0059 & 1.054 \\ \hline
	  3 & 800 & 0.0177 & 0.0105 & 0.593 \\ \hline
	  4 & 1600 & 0.0185 & 0.0165 & 0.892 \\ \hline
	  5 & 3200 & 0.0185 & 0.0397 & 2.146 \\ \hline
	  6 & 6400 & 0.0225 & 0.1089 & 4.840 \\ \hline
	  7 & 12800 & 0.0258 & 0.3837 & 14.872 \\ \hline
	  8 & 25600 & 0.0336 & 1.4815 & 44.092 \\ \hline
	  9 & 51200 & 0.0362 & 5.8872 & 162.630 \\ \hline
	  10 & 102400 & 0.0612 & 23.4358 & 382.938 \\ \hline
	  11 & 204800 & 0.1128 & 93.586 & 829.663 \\ \hline
	  12 & 409600 & 0.2099 & 375.471 & 1788.809 \\ \hline
	  13 & 819200 & 0.4106 & 1501.25 & 3656.235 \\ \hline
	  14 & 1638400 & 0.8334 & $\infty$ & $\infty$ \\ \hline
	  15 & 3276800 & 1.6964 & $\infty$ & $\infty$ \\ \hline
	  16 & 6553600 & 3.4603 & $\infty$ & $\infty$ \\ \hline
	\end{tabular}
      \end{center}
      \caption{Archivos Random}
      \label{tabla 3}
    \end{table}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{msrandom.png}
      \caption{Tiempos usando el algoritmo mergesort en función del tamaño del array para arrays aleatorios}
      \label{fig:7}
    \end{figure}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{ssrandom.png}
      \caption{Tiempos usando el algoritmo selection sort en función del tamaño del array para arrays aleatorios}
      \label{fig:8}
    \end{figure}

    \begin{figure}[H]
      \centering
      \includegraphics[width=0.9\textwidth]{speeduprandom.png}
      \caption{Speedup para arrays aleatorios en función de N}
      \label{fig:9}
    \end{figure}

\FloatBarrier

\section{Profiling}
  \begin{itemize}
   \item \emph{¿Qué tamaño de muestra nos conviene más tomar para hacer el profiling?}
    \vspace{0.2cm}

    Para que \emph{gprof} pueda calcular los tiempos de ejecución que ocupa cada función del código con precisión, es conveniente tomar un tamaño de muestra tal que al programa le lleve un tiempo apreciable procesarla. De otra forma, si se eligiese una muestra muy pequeña que pueda ser ordenada instantáneamente, el reporte emitido por la aplicación de profiling podría indicar que la ejecución del programa llevó 0 segundos. En este caso, la muestra es un archivo con un arreglo de 300.000 bytes, generado aleatoriamente. Se eligió ese tamaño por ser lo bastante grande como para permitir una buena medición sin demorar demasiado esta tarea.

   \item \emph{Si tuviera que elegir una y sólo una función para optimizar (asumiendo que cualquiera puede ser arbitrariamente optimizada), ¿Cuál elegiría? ¿Cuál sería el speedup máximo obtenible mediante la optimización de esa función?}
   \end{itemize}
   \vspace{0.3cm}

   La ejecución de gprof arrojó los siguientes datos:
   \begin{verbatim}
       cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
100.28    192.07   192.07        1   192.07   192.08  selectionSort
  0.01    192.08     0.01   298853     0.00     0.00  swap
  0.00    192.08     0.00        1     0.00     0.00  abrirArchivo
  0.00    192.08     0.00        1     0.00     0.00  escribirSalida
  0.00    192.08     0.00        1     0.00     0.00  leerArchivoYObtenerDatos
  0.00    192.08     0.00        1     0.00   192.08  ordenarConSelectionSort
  0.00    192.08     0.00        1     0.00   192.08  ordenarSegunAlgoritmoElegido
   \end{verbatim}
   Puede verse que la función \emph{selectionSort} ocupa prácticamente todo el tiempo de ejecución de la aplicación (en realidad el porcentaje de tiempo que figura no es correcto; si el tiempo total de ejecución es de 192,08s y el tiempo ocupado por la función es 192,07, el porcentaje de tiempo que ocupa es 99,99\%), mientras que a la función swap le corresponde solamente el 0,01\%, y el resto ni siquiera llegan a ser tenidas en cuenta por \emph{gprof}, por lo que las consideraremos despreciables.
   \vspace{0.2cm}
   
   Por ocupar una fracción tan grande de tiempo, la función que conviene elegir para optimizar es \emph{selectionSort}
   \vspace{0.3cm}

   En cuanto al speedup máximo obtenible, es áquel que se lograría con un speedup local tendiendo a infinito. Aplicando la ley de Amdahl, se obtiene:
   \[\lim_{S_{L} \to \infty} S_{G} = \frac{1}{(1 - 0,99) + \frac{0,99}{S_{L}}}\]
   \[\Rightarrow S_{G_{max}} = 100 \]

\section{Pruebas}
      \begin{itemize}
      \item \textbf{Datos desde archivo y stdin: }
      Si ejecutamos la siguiente secuencia de comandos en el shell:\\
      \$echo -n ``abcd'' $>$ letras.txt \\
      \$echo 1234 $|$ ./tp0 -m letras.txt  \\
      abcd\$ \\
      En este caso, cuando se ingresen datos tanto desde archivos como desde stdin, sólo se tendrán en cuenta los primeros, 
      ignorando los que provengan de la entrada estándard. \\
      
      \item \textbf{Selección de un algoritmo por defecto: }
      Se puede observar que es posible no explicitar un algoritmo de ordenamiento. En este caso se utiliza \emph{Merge-sort} por defecto.\\
      \$echo ``cba'' $|$ ./tp0 \\
      abc\$ \\

      \item \textbf{Selección de más de un algoritmo de ordenamiento: } 
      La elección de más de un algoritmo de ordenamiento no corta el flujo de la aplicación. 
      Se considera como válido al primero de ellos. \\
      \$echo ``cba'' $|$ ./tp0 -m -s\\
      abc\$ \\
      
      \item \textbf{Selección de un archivo inexistente: }
      Si consideramos  que el archivo ``letras.txt'' ya fue creado, y que ``numeros.txt'' no existe en el directorio actual,
      la ejecución del programa pasando por parámetro algún archivo inválido, corta el flujo de la aplicación y muestra el error 
      por stderr. \\
      \$./tp0 letras.txt numeros.txt 2$>$ error.out \\
      \$cat error.out\\
      No se pudo abrir el archivo: numeros.txt en modo rb \\

      \item \textbf{Selección de multiples archivos: }
      Ejecutando los siguientes comandos y considerando que el archivo ``letras.txt'' ya se encuentra en el directorio: \\
      \$echo -n ``ihjk'' $>$ letras2.txt \\
      \$./tp0 -m letras2.txt letras.txt \\ 
      abcdhijk\$ \\
      Se puede observar que ambos archivos fueron ordenados. \\
      

      \item \textbf{Ayuda: } \\
      \$./tp0 -h\\
      tp0 [OPTIONS][file...] \\
      -h, --help           display this help and exit.\\
      -V, --version        display version information and exit.\\
      -m, --merge          use the mergesort algorithm.\\
      -s, --sel            use the selectionsort algorithm.\\ \\
      Muestra la ayuda del programa.\\ 
      \item \textbf{Versión: } \\
      \$./tp0 -v 
      \$Versión: 1.0 \\\\
      Muestra la versión del programa. \\
      \item \textbf{Parámetro inválido: } \\
      La introducción de un parámetro inválido muestra el mensaje de ayuda. \\ \\
      \$./tp0 --Version\\
      \$./tp0: unrecognized option '--Version'\\
      tp0 [OPTIONS][file...] \\
      -h, --help           display this help and exit.\\
      -V, --version        display version information and exit.\\
      -m, --merge          use the mergesort algorithm.\\
      -s, --sel            use the selectionsort algorithm.\\

      \end{itemize}

\section{Conclusión}
     Luego de realizar las secciones de profiling y de mediciones podemos observar empíricamente la relación que 
     existe entre la ley de Amdahl y los resultados obtenidos. \\

     En primer lugar, la ley establece que el tiempo nuevo de ejecución es inversamente proporcional a una función
     [(1 - f) + f / SM] que depende de la fracción de tiempo en la cual corren los procesos que se pueden optimizar. 
     Es por ello que si nuestro programa pasa mucho tiempo ejecutando una determinada función, 
     es sobre esta misma sobre la cual se intentará realizar una mejora. \\

     En segundo lugar, la misma función determina que el nuevo tiempo de ejecución de un proceso está limitado
     por la fracción tiempo en que dicho proceso no puede ser mejorado. Si logramos mejorar algún recurso en un factor SM, 
     el speed up obtenido estará acotado. Esto quiere decir que por mucho que incrementemos SM, el tiempo nuevo de ejecución
     no podrá ser superior a 1 / 1 - f. Si el recurso que mejoramos es un cuello de botella,  f será elevada  y, en consecuencia, 
     la cota superior será también elevada. En contraposición, si el recurso al cual se le aplica la 
     mejora es utilizado poco por la aplicación, f será un valor cercano a cero y la cota resultará más baja.



 \begin{thebibliography}{99}

 \bibitem{WWW} "Documentación librería GetOpt" \url{http://www.gnu.org/software/libc/manual/html_node/Getopt.html}
 \end{thebibliography}
\end{document}


